package day_6_26;

public class Main1 {
    /**
     * 32. 最长有效括号
     * https://leetcode.cn/problems/longest-valid-parentheses/description/
     */
    public int longestValidParentheses(String s) {
        int n = s.length();
        int[] dp = new int[n];
        int ret = 0;
        for(int i = 1;i < n;i++) {
            if(s.charAt(i) == ')') {
                if(s.charAt(i - 1) == '(') {
                    dp[i] = (i >= 2 ? dp[i - 2] : 0) + 2;
                }else if(i - dp[i - 1] > 0 && s.charAt(i - dp[i - 1] - 1) == '('){
                    // 说明当前的 ')' 在越过前面的最长有效括号之后，就是'(' 那么就可以进行组合
                    dp[i] = dp[i - 1] + (i - dp[i - 1] >= 2 ? dp[i - dp[i - 1] - 2] : 0) + 2;
                }
            }
            ret = Math.max(ret,dp[i]);
        }
        return ret;
    }
}
